This invention relates to a pattern matching device for carrying out pattern matching between two patterns by calculating a similarity or likelihood measure between the patterns.
Each pattern may be given by a spoken word or a plurality of continuously spoken words. Alternatively, the pattern may be a figure or diagram which, in turn, may be type-printed characters or hand-printed letters. The pattern matching device serves as a main structural unit of a pattern recognition system as disclosed in U.S. Pat. No. 3,816,722 issued to Hiroaki Sakoe, the present applicant, et al, assignors to Nippon Electric Co., Ltd., the instant assignee. Such a device is useful also in a continuous speech recognition system as revealed in U.S. Pat. No. 4,059,725 issued to Hiroaki Sakoe, the instant applicant, and assigned to the present assignee.
The dynamic programming technique or algorithm as called in the art, is resorted to in a majority of pattern matching devices which are now in actual use. According to the dynamic programming technique, the two patterns are represented by a first and a second sequence of feature vectors, respectively. Each sequence consists of a certain number of feature vectors depending on the pattern represented by that sequence. A primitive similarity measure is calculated between each feature vector of the first sequence and each feature vector of the second sequence. A recurrence formula is calculated, which defines a recurrence value by a sum of each primitive similarity measure and an extremum of a prescribed number of previously calculated recurrence values. The extremum is a minimum and a maximum when the primitive similarity measure is given, for example, by a distance measure and a correlation measure between the two feature vectors, respectively. The recurrence formula eventually gives an eventual similarity measure representative of whether the two patterns are similar or dissimilar to each other.
For a pattern recognition system, a plurality of reference patterns are preliminarily registered therein as reference feature vector sequences. An unknown pattern to be recognized, is supplied to the system as an input feature vector sequence. The unknown pattern is subjected to the pattern matching successively with the reference patterns. The unknown pattern is recognized as one of the reference patterns that provides an extremum eventual similarity measure relative to the unknown pattern.
As will later be discussed in detail with reference to a few of about ten figures of the accompanying drawing, a conventional pattern matching device comprises a work memory and a calculating circuit which must deal with signals having a multiplicity of bits particularly when the pattern to be subjected to the pattern matching is represented by a sequence of a considerably great number of feature vectors. In other words, signals processed by the work memory and the calculating circuit or circuits, must have a wide dynamic range. The pattern matching devices have therefore been relatively bulky and expensive. It has furthermore been inconvenient to implement such devices by the known integrated semiconductor circuit technique.
On the other hand, it has been known as described in an article which Fumitada Itakura contributed to IEEE Transactions of Acoustics, Speech, and Signal Processing, Volume ASSP-23, No. 1 (February 1975), pages 67-72, under the title of "Minimum Prediction Residual Principle Applied to Speech Recognition," that the speed of pattern recognition can be increased by rejecting or discontinuing the pattern matching in a pattern recognition system when the reference pattern being subjected to the pattern matching, gives a distance measure greater than a predetermined threshold.